<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3418：Poi2013  Tapestries</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013  Tapestries</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Poi2013  Tapestries</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Poi2013  Tapestries                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">An exhibition of tapestries is opening in Byteotian Museum of Fine Arts. The main exhibition room, viewed from top, is a polygon (not necessarily convex). A tapestry is hanged on each wall of the room, each tapestry taking all the area of its wall.<br />
A lamp has been installed in the room in order to illuminate the exhibition. The lamp is glowing uniformly in all directions. However, while some of the tapestries have to be flooded with light, others cannot be exposed to strong light.<br />
Byteasar, the curator, has been moving the lamp around the room, but so far he is not satisfied with the results. Now he is terrified by the prospect of moving the tapestries around instead - this would require much effort, and the exhibition is to open soon. Perhaps you will be able to tell him if his attempts are doomed or not?<br />
Your task is to determine if there is such a spot that placing the lamp in it satisfies the following:<br />
&bull;&nbsp;each wall is to be either completely illuminated or completely shaded, as required by the tapestry hanging on it; there can be no wall that is partly illuminated and partly shaded;<br />
&bull;&nbsp;if the lamp is located exactly on the wall or its extension, this wall is not illuminated;<br />
&bull;&nbsp;the lamp can neither be switched off nor taken away from the room; it has to be on while located (strictly) inside the room (i.e., it cannot be placed in a corner or on any wall).<br />
</span></p>
<p><span style="font-family: 宋体; font-size: 14px; line-height: 20.909090042114258px;">给定一个不自交、无重点、无三点共线的多边形，多边形每条边都被要求必须有灯光直射或者必须没有，只有一部分照射或者没有照射到都是不合法的。求问是否存在一个点能够满足这个条件。</span></p></p><hr/><h3>输入格式</h3><p><p><font size="4">There is a single integer t (1&lt;=t&lt;=20) in the first line of the standard input, denoting the number of data sets. The following lines describe these data sets.<br />
The first line of a single description holds a single integer N （3&lt;=N&lt;=1000）, denoting the number of walls in the main exhibition room. Then the following N lines specify the room's shape. Each of those lines contains a pair of integers Xi and Yi (-30000&lt;=Xi,Yi&lt;=30000) for i=1,2&hellip;N, separated by a single space, denoting the coordinates of the room's corner or, in other words, the vertex of corresponding polygon. The vertices are given clockwise.<br />
The next n lines specify the tapestries' requirements. Each of those lines contains a single letter, S or C, denoting that the wall has to be illuminated or shaded, respectively. The letter in the i-th of these lines （for 1&lt;=i&lt;=N-1） regards the wall between the&nbsp; -th and the (i+1)-th vertex. The letter in the last of these lines regards the wall between the last and the first vertex.<br />
The polygon depicting the room's shape has no self-crossings, i.e., with the exception of successive sides, which share a common vertex, no two sides of the polygon share a common point. Furthermore, no three vertices of the polygon are collinear.<br />
</font></p>
<p><span style="font-size: 14px; line-height: 20.909090042114258px; font-family: 宋体;">第一行一个</span><span lang="EN-US" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;">t</span><span style="font-size: 14px; line-height: 20.909090042114258px; font-family: 宋体;">代表数据组数</span></p>
<p class="MsoNormal" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;"><span style="font-family: 宋体;">每组数据第一行一个</span><span lang="EN-US">n</span><span style="font-family: 宋体;">代表多边形点数</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;"><span style="font-family: 宋体;">接下来</span><span lang="EN-US">n</span><span style="font-family: 宋体;">行每行一个数代表第</span><span lang="EN-US">i</span><span style="font-family: 宋体;">个点的坐标，点按顺时针顺序给出。</span><span lang="EN-US"><o:p></o:p></span></p>
<p class="MsoNormal" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;"><span style="font-family: 宋体;">最后</span><span lang="EN-US">n</span><span style="font-family: 宋体;">行每行一个</span><span lang="EN-US">S</span><span style="font-family: 宋体;">（代表需要照射）或者</span><span lang="EN-US">C</span><span style="font-family: 宋体;">（代表不需要照射）。前</span><span lang="EN-US">n-1</span><span style="font-family: 宋体;">行第</span><span lang="EN-US">i</span><span style="font-family: 宋体;">行的边是第</span><span lang="EN-US">i</span><span style="font-family: 宋体;">个给定的点和第</span><span lang="EN-US">i+1</span><span style="font-family: 宋体;">个给定的点的边，最后一行的边是第</span><span lang="EN-US">1</span><span style="font-family: 宋体;">和</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个点之间的边。</span><span lang="EN-US"><o:p></o:p></span></p>
<p></p></p><hr/><h3>输出格式</h3><p><p><font size="4">For each data set your program should print to the standard output a single line containing a single word:<br />
&bull;&nbsp;TAK (Polish for yes) if the lamp can be placed so as to satisfy all aforementioned requirements, or<br />
&bull;&nbsp;NIE (Polish for no) otherwise.<br />
Example<br />
In the figures below the examples, the thick sides denote the walls that have to be shaded while the remaining sides - the walls that have to be illuminated. The figure for the first example shows a correct placement of the lamp.<br />
</font></p>
<p><span style="font-size: 14px; line-height: 20.909090042114258px; font-family: 宋体;">每行一个</span><span lang="EN-US" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;">TAK</span><span style="font-size: 14px; line-height: 20.909090042114258px; font-family: 宋体;">（代表存在）或</span><span lang="EN-US" style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 20.909090042114258px;">NIE</span><span style="font-size: 14px; line-height: 20.909090042114258px; font-family: 宋体;">（代表不存在）</span></p></p><hr/><h3>样例输入</h3><pre>1
16
5 -3
4 -4
3 -7
0 -5
-3 -7
-4 -4
-5 -3
-1 -1
-4 3
-2 4
-1 2
0 7
1 2
2 4
4 3
1 -1
C
S
S
S
S
C
C
S
S
C
S
S
C
S
S
C
        
 


</pre><hr/><h3>样例输出</h3><pre>TAK
</pre><hr/><h3>提示</h3><p><p><img height="265" width="198" alt="" src="../file/3418_0.jpg" /></p></p><hr/><h3>题目来源</h3><p>鸣谢HJWJBSR提供译文</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3418" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3418" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>